//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "functional.h"
#include "binary_search.h"
#include "sort.h"
#include "utility.h"
#include "vector.h"

FC_NAMESPACE_BEGIN


template <class Key, class Compare, class Allocator>
class vector_set : public vector<Key, Allocator>
{
public:
	typedef vector_set<Key, Compare, Allocator>			this_type;
	typedef vector<Key, Allocator>						base_type;
	typedef Key											key_type;
	typedef Compare										key_compare;
	typedef key_compare									value_compare;
	typedef typename base_type::size_type				size_type;
	typedef typename base_type::value_type				value_type;
	typedef typename base_type::pointer					pointer;
	typedef typename base_type::const_pointer			const_pointer;
	typedef typename base_type::reference				reference;
	typedef typename base_type::const_reference			const_reference;
	typedef typename base_type::iterator				iterator;
	typedef typename base_type::const_iterator			const_iterator;
	typedef typename base_type::allocator_type			allocator_type;

	using base_type::begin;
	using base_type::end;
	using base_type::rbegin;
	using base_type::rend;
	using base_type::size;
	using base_type::empty;
	using base_type::full;
	using base_type::capacity;
	using base_type::get_allocator;
	using base_type::set_allocator;
	using base_type::erase_at;
	using base_type::clear;
	using base_type::reset;
	using base_type::data;
	using base_type::front;
	using base_type::back;
	using base_type::pop_back;
	using base_type::reserve;
	using base_type::set_capacity;
	using base_type::shrink_to_fit;
	using base_type::iterator_is_valid;
	using base_type::swap;
	using base_type::at;
	using base_type::operator[];


	vector_set()
		: base_type(), m_compare()
		{
		}

	explicit vector_set( const allocator_type& alloc )
		: base_type(alloc), m_compare()
		{
		}

	explicit vector_set( const Compare& comp, const allocator_type& alloc = allocator_type() )
		: base_type(alloc), m_compare(comp)
		{
		}

	template<class InputIterator>
		vector_set( InputIterator first, InputIterator last, const Compare& comp = Compare(), const allocator_type& alloc = allocator_type() )
		: base_type(first, last, alloc), m_compare(comp)
		{
			sort();
		}

	vector_set( const this_type& x )
		: base_type(x), m_compare(x.m_compare)
		{
		}

	this_type& operator =( const this_type& x )
	{
		if( this != &x )
		{
			base_type::operator =(x);
			m_compare = x.m_compare;
		}
		return *this;
	}

	this_type& operator =( const base_type& x )
	{
		if( this != &x )
		{
			base_type::operator =(x);
			sort();
		}
		return *this;
	}

	void push_back( const value_type& value )
	{
		insert(value);
	}

	pair<iterator, bool> insert( const value_type& value )
	{
		pair<iterator, bool> ret( lower_bound(value), false );
		if( ret.first == end() || m_compare(value, *ret.first) )
		{
			ret.first = base_type::insert( ret.first, value );
			ret.second = true;
		}

		return ret;
	}

	iterator insert( iterator it, const value_type& value )
	{
		return insert(value).first;
	}

	template <class InputIterator>
	void insert( InputIterator first, InputIterator last )
	{
		base_type::insert(begin(), first, last);
		sort();
	}

	void erase( iterator it ) { base_type::erase(it); }
	void erase( iterator first, iterator last ) { base_type::erase(first, last); }

	size_t erase( const key_type& key )
    {
		size_t n(0);
		iterator it = find(key);
        if( it != end() )
		{
			erase(it);
			++n;
		}
		return n;
	}

	bool contains( const key_type& key ) const
    {
		return find(key) != end();
	}

	iterator find( const key_type& key )
    {
		iterator it = lower_bound(key);
		if( it != end() && m_compare(key, *it) )
			it = end();
		return it;
	}

    const_iterator find( const key_type& key ) const
    {
		const_iterator it = lower_bound(key);
		if( it != end() && m_compare(key, *it) )
			it = end();
		return it;
	}

	size_t count( const key_type& key ) const
	{
		return( find(key) != end() ? (size_type)1 : (size_type)0 );
	}

	key_compare key_comp() const { return m_compare; }
	value_compare value_comp() const { return key_comp(); }

	pair<iterator, iterator> equal_range( const key_type& key )
	{
		iterator first = lower_bound(key);
		iterator last = first;
		if( !(first != end() && m_compare(key, *first)) )
			++last;
		return pair<iterator, iterator>(first, last);
	}

	pair<const_iterator, const_iterator> equal_range( const key_type& key ) const
	{
		const_iterator first = lower_bound(key);
		const_iterator last = first;
		if( !(first != end() && m_compare(key, *first)) )
			++last;
		return pair<const_iterator, const_iterator>(first, last);
	}

	iterator lower_bound( const key_type& key )
	{
		return fc::lower_bound( begin(), end(), key, m_compare );
	}

	const_iterator lower_bound( const key_type& key ) const
	{
		return fc::lower_bound( begin(), end(), key, m_compare );
	}

	iterator upper_bound( const key_type& key )
	{
		return fc::upper_bound( begin(), end(), key, m_compare );
	}

	const_iterator upper_bound( const key_type& key ) const
	{
		return fc::upper_bound( begin(), end(), key, m_compare );
	}

	void sort()
	{
		if( size() > (size_type)1 )
		{
			fc::sort( begin(), end(), m_compare );
			iterator it = fc::unique( begin(), end() );
			if( it != end() )
				base_type::erase( it, end() );
		}
	}

protected:
	key_compare m_compare;
};



FC_NAMESPACE_END
